home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / Other Langs / mpw yacc ƒ src / genstates.c < prev    next >
C/C++ Source or Header  |  1989-11-19  |  9KB  |  519 lines
  1. #include <stdio.h>
  2. #include "defs.h"
  3. #include "dep.h"
  4. #include "new.h"
  5. #include "gram.h"
  6. #include "state.h"
  7.  
  8. #define    STATE_TABLE_SIZE    1009
  9.  
  10. extern short *itemset;
  11. extern short *itemsetend;
  12. extern unsigned *ruleset;
  13.  
  14. int nstates;
  15. int final_state;
  16. core *first_state;
  17. shifts *first_shift;
  18. reductions *first_reduction;
  19.  
  20. int get_state();
  21. core *new_state();
  22.  
  23. static core *this_state;
  24. static core *last_state;
  25. static shifts *last_shift;
  26. static reductions *last_reduction;
  27.  
  28. static int nshifts;
  29. static short *shift_symbol;
  30.  
  31. static short *redset;
  32. static short *shiftset;
  33.  
  34. static short **kernel_base;
  35. static short **kernel_end;
  36. static short *kernel_items;
  37.  
  38. static core **gen_state_table;
  39.  
  40.  
  41. allocate_itemsets()
  42. {
  43.   register short *itemp;
  44.   register short *item_end;
  45.   register int symbol;
  46.   register int i;
  47.   register int count;
  48.   register int max;
  49.   register short *symbol_count;
  50.  
  51.   count = 0;
  52.   symbol_count = NEW2(nsyms, short);
  53.  
  54.   item_end = ritem + nitems;
  55.   for (itemp = ritem; itemp < item_end; itemp++)
  56.     {
  57.       symbol = *itemp;
  58.       if (symbol > 0)
  59.     {
  60.       count++;
  61.       symbol_count[symbol]++;
  62.     }
  63.     }
  64.  
  65.   kernel_base = NEW2(nsyms, short *);
  66.   kernel_items = NEW2(count, short);
  67.  
  68.   count = 0;
  69.   max = 0;
  70.   for (i = 0; i < nsyms; i++)
  71.     {
  72.       kernel_base[i] = kernel_items + count;
  73.       count += symbol_count[i];
  74.       if (max < symbol_count[i])
  75.     max = symbol_count[i];
  76.     }
  77.  
  78.   shift_symbol = symbol_count;
  79.   kernel_end = NEW2(nsyms, short *);
  80. }
  81.  
  82.  
  83.  
  84. allocate_storage()
  85. {
  86.   allocate_itemsets();
  87.  
  88.   shiftset = NEW2(nsyms, short);
  89.   redset = NEW2(nrules + 1, short);
  90.   gen_state_table = NEW2(STATE_TABLE_SIZE, core *);
  91. }
  92.  
  93.  
  94.  
  95. append_states()
  96. {
  97.   register int i;
  98.   register int j;
  99.   register int symbol;
  100.  
  101. #ifdef    TRACE
  102.   fprintf(stderr, "Entering append_states\n");
  103. #endif
  104.  
  105.   for (i = 1; i < nshifts; i++)
  106.     {
  107.       symbol = shift_symbol[i];
  108.       j = i;
  109.       while (j > 0 && shift_symbol[j - 1] > symbol)
  110.     {
  111.       shift_symbol[j] = shift_symbol[j - 1];
  112.       j--;
  113.     }
  114.       shift_symbol[j] = symbol;
  115.     }
  116.  
  117.   for (i = 0; i < nshifts; i++)
  118.     {
  119.       symbol = shift_symbol[i];
  120.       shiftset[i] = get_state(symbol);
  121.     }
  122. }
  123.  
  124.  
  125. augment_automaton()
  126. {
  127.     register int i, k;
  128.     register core *statep, *ostatep;
  129.     register shifts *sp;
  130.  
  131.     ostatep = first_state;
  132.     statep = first_state->next;
  133.     while (statep && ISTOKEN(statep->accessing_symbol))
  134.     {
  135.     ostatep = statep;
  136.     statep = statep->next;
  137.     }
  138.     k = ostatep->number;
  139.  
  140.     final_state = nstates;
  141.     nstates++;
  142.     statep = NEW(core);
  143.     statep->number = final_state;
  144.     statep->accessing_symbol = start_symbol;
  145.     statep->nitems = 1;
  146.     statep->items[0] = 2;
  147.     last_state->next = statep;
  148.     last_state = statep;
  149.  
  150.     sp = (shifts *) ALLOC(sizeof(shifts) +
  151.             first_shift->nshifts * sizeof(short));
  152.     sp->next = first_shift->next;
  153.     sp->nshifts = first_shift->nshifts + 1;
  154.     for (i = first_shift->nshifts; i > 0; i--)
  155.     {
  156.     if (first_shift->shifts[i-1] > k)
  157.         sp->shifts[i] = first_shift->shifts[i-1];
  158.     else
  159.         break;
  160.     }
  161.     sp->shifts[i] = final_state;
  162.     for (i--; i >= 0; i--)
  163.     sp->shifts[i] = first_shift->shifts[i];
  164.  
  165.     FREE(first_shift);
  166.     first_shift = sp;
  167. }
  168.  
  169.  
  170. free_storage()
  171. {
  172.   FREE(shift_symbol);
  173.   FREE(redset);
  174.   FREE(shiftset);
  175.   FREE(kernel_base);
  176.   FREE(kernel_end);
  177.   FREE(kernel_items);
  178.   FREE(gen_state_table);
  179. }
  180.  
  181.  
  182.  
  183. generate_states()
  184. {
  185.   allocate_storage();
  186.   itemset = NEW2(nitems, short);
  187.   ruleset = NEW2(WORDSIZE(nrules), unsigned);
  188.   set_first_derives();
  189.   initialize_states();
  190.  
  191.   while (this_state)
  192.     {
  193.       closure(this_state->items, this_state->nitems);
  194.       save_reductions();
  195.       new_itemsets();
  196.       append_states();
  197.  
  198.       if (nshifts > 0)
  199.         save_shifts();
  200.  
  201.       this_state = this_state->next;
  202.     }
  203.  
  204.   finalize_closure();
  205.   free_storage();
  206.   augment_automaton();
  207. }
  208.  
  209.  
  210.  
  211. int
  212. get_state(symbol)
  213. int symbol;
  214. {
  215.   register int key;
  216.   register short *isp1;
  217.   register short *isp2;
  218.   register short *iend;
  219.   register core *sp;
  220.   register int found;
  221.  
  222.   int n;
  223.  
  224. #ifdef    TRACE
  225.   fprintf(stderr, "Entering get_state, symbol = %d\n", symbol);
  226. #endif
  227.  
  228.   isp1 = kernel_base[symbol];
  229.   iend = kernel_end[symbol];
  230.   n = iend - isp1;
  231.  
  232.   key = 0;
  233.   while (isp1 < iend)
  234.     key += *isp1++;
  235.  
  236.   key = key % STATE_TABLE_SIZE;
  237.  
  238.   sp = gen_state_table[key];
  239.  
  240.   if (sp)
  241.     {
  242.       found = 0;
  243.       while (!found)
  244.     {
  245.       if (sp->nitems == n)
  246.         {
  247.           found = 1;
  248.           isp1 = kernel_base[symbol];
  249.           isp2 = sp->items;
  250.  
  251.           while (found && isp1 < iend)
  252.         {
  253.           if (*isp1++ != *isp2++)
  254.             found = 0;
  255.         }
  256.         }
  257.  
  258.       if (!found)
  259.         {
  260.           if (sp->link)
  261.         {
  262.           sp = sp->link;
  263.         }
  264.           else
  265.         {
  266.           sp = sp->link = new_state(symbol);
  267.           found = 1;
  268.         }
  269.         }
  270.     }
  271.     }
  272.   else
  273.     {
  274.       gen_state_table[key] = sp = new_state(symbol);
  275.     }
  276.  
  277.   return (sp->number);
  278. }
  279.  
  280.  
  281.  
  282. initialize_states()
  283. {
  284.   register core *p;
  285.  
  286.   p = NEW(core);
  287.   p->nitems = 1;
  288.   p->items[0] = rrhs[0];
  289.   first_state = last_state = this_state = p;
  290.   nstates = 1;
  291. }
  292.  
  293.  
  294. new_itemsets()
  295. {
  296.   register int i;
  297.   register int shiftcount;
  298.   register short *isp;
  299.   register short *ksp;
  300.   register int symbol;
  301.  
  302. #ifdef    TRACE
  303.   fprintf(stderr, "Entering new_itemsets\n");
  304. #endif
  305.  
  306.   for (i = 0; i < nsyms; i++)
  307.     kernel_end[i] = NULL;
  308.  
  309.   shiftcount = 0;
  310.  
  311.   isp = itemset;
  312.  
  313.   while (isp < itemsetend)
  314.     {
  315.       i = *isp++;
  316.       symbol = ritem[i];
  317.       if (symbol > 0)
  318.     {
  319.           ksp = kernel_end[symbol];
  320.  
  321.           if (!ksp)
  322.         {
  323.           shift_symbol[shiftcount++] = symbol;
  324.           ksp = kernel_base[symbol];
  325.         }
  326.  
  327.           *ksp++ = i + 1;
  328.           kernel_end[symbol] = ksp;
  329.     }
  330.     }
  331.  
  332.   nshifts = shiftcount;
  333. }
  334.  
  335.  
  336.  
  337. core *
  338. new_state(symbol)
  339. int symbol;
  340. {
  341.   register int n;
  342.   register core *p;
  343.   register short *isp1;
  344.   register short *isp2;
  345.   register short *iend;
  346.  
  347. #ifdef    TRACE
  348.   fprintf(stderr, "Entering new_state, symbol = %d\n", symbol);
  349. #endif
  350.  
  351.   if (nstates >= MAXSHORT)
  352.     fatal("too many states");
  353.  
  354.   isp1 = kernel_base[symbol];
  355.   iend = kernel_end[symbol];
  356.   n = iend - isp1;
  357.  
  358.   p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
  359.   p->accessing_symbol = symbol;
  360.   p->number = nstates;
  361.   p->nitems = n;
  362.  
  363.   isp2 = p->items;
  364.   while (isp1 < iend)
  365.     *isp2++ = *isp1++;
  366.  
  367.   last_state->next = p;
  368.   last_state = p;
  369.  
  370.   nstates++;
  371.  
  372.   return (p);
  373. }
  374.  
  375.  
  376. /* show_cores is used for debugging */
  377.  
  378. show_cores()
  379. {
  380.     core *p;
  381.     int i, j, k;
  382.  
  383.     k = 0;
  384.     for (p = first_state; p; ++k, p = p->next)
  385.     {
  386.     if (k) printf("\n");
  387.     printf("state %d, number = %d, accessing symbol = %d\n",
  388.         k, p->number, p->accessing_symbol);
  389.     j = p->nitems;
  390.     for (i = 0; i < j; ++i)
  391.         printf("\t%d\n", p->items[i]);
  392.     }
  393. }
  394.  
  395.  
  396. /* show_ritems is used for debugging */
  397.  
  398. show_ritems()
  399. {
  400.     int i;
  401.  
  402.     for (i = 0; i < nitems; ++i)
  403.     printf("ritem[%d] = %d\n", i, ritem[i]);
  404. }
  405.  
  406.  
  407. /* show_rrhs is used for debugging */
  408. show_rrhs()
  409. {
  410.     int i;
  411.  
  412.     for (i = 0; i < nrules; ++i)
  413.     printf("rrhs[%d] = %d\n", i, rrhs[i]);
  414. }
  415.  
  416.  
  417. /* show_shifts is used for debugging */
  418.  
  419. show_shifts()
  420. {
  421.     shifts *p;
  422.     int i, j, k;
  423.  
  424.     k = 0;
  425.     for (p = first_shift; p; ++k, p = p->next)
  426.     {
  427.     if (k) printf("\n");
  428.     printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
  429.         p->nshifts);
  430.     j = p->nshifts;
  431.     for (i = 0; i < j; ++i)
  432.         printf("\t%d\n", p->shifts[i]);
  433.     }
  434. }
  435.  
  436.  
  437. save_shifts()
  438. {
  439.   register shifts *p;
  440.   register short *sp1;
  441.   register short *sp2;
  442.   register short *send;
  443.  
  444.   p = (shifts *) allocate((unsigned) (sizeof(shifts) +
  445.             (nshifts - 1) * sizeof(short)));
  446.  
  447.   p->number = this_state->number;
  448.   p->nshifts = nshifts;
  449.  
  450.   sp1 = shiftset;
  451.   sp2 = p->shifts;
  452.   send = shiftset + nshifts;
  453.  
  454.   while (sp1 < send)
  455.     *sp2++ = *sp1++;
  456.  
  457.   if (last_shift)
  458.     {
  459.       last_shift->next = p;
  460.       last_shift = p;
  461.     }
  462.   else
  463.     {
  464.       first_shift = p;
  465.       last_shift = p;
  466.     }
  467. }
  468.  
  469.  
  470.  
  471. save_reductions()
  472. {
  473.   register short *isp;
  474.   register short *rp1;
  475.   register short *rp2;
  476.   register int item;
  477.   register int count;
  478.   register reductions *p;
  479.  
  480.   short *rend;
  481.  
  482.   count = 0;
  483.   for (isp = itemset; isp < itemsetend; isp++)
  484.     {
  485.       item = ritem[*isp];
  486.       if (item <= 0)
  487.     {
  488.       redset[count++] = -item;
  489.     }
  490.     }
  491.  
  492.   if (count)
  493.     {
  494.       p = (reductions *) allocate((unsigned) (sizeof(reductions) +
  495.                     (count - 1) * sizeof(short)));
  496.  
  497.       p->number = this_state->number;
  498.       p->nreds = count;
  499.  
  500.       rp1 = redset;
  501.       rp2 = p->rules;
  502.       rend = rp1 + count;
  503.  
  504.       while (rp1 < rend)
  505.     *rp2++ = *rp1++;
  506.  
  507.       if (last_reduction)
  508.     {
  509.       last_reduction->next = p;
  510.       last_reduction = p;
  511.     }
  512.       else
  513.     {
  514.       first_reduction = p;
  515.       last_reduction = p;
  516.     }
  517.     }
  518. }
  519.